Міністерство Освіти і Науки України Національний Університет “Львівська Політехніка”
Кафедра ЕОМ Елементи теорії множин II Методичні вказівкидо практичних занять та самостійної роботи з курсу “Дискретна математика”для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” Затвердженона засіданні кафедриЕлектронних Обчислювальних МашинПротокол № 9 від 17 квітня 2003 року Львів – 2003  Елементи теорії множин II : Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: І. Мороз, Р. Попович – Львів: Національний університет “Львівська політехніка”, 2003, 13 с. Укладачі: І. Мороз, старший викладач Р. Попович, к.т.н., доцент Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н. Юрчак І. Ю., доцент кафедри САПР, к. т. н. Елементи теорії множин II Відношення Розглянемо декартовий добуток к-го степеня множини Х: Хк = Х ( Х ( ... ( Х. Довільну підмножину R множини Хк (R ( Хк) будемо називати к-арним відношенням, заданим на множині Х. Вважатимемо, що впорядковані елементи x1, x2, …, xn ( Х знаходяться між собою у відношенні R, коли (x1, x2, …, xn) ( R. Одномісні відношення, які ще називаються унітарними, відповідають підмножинам множини X. Надалі особливу увагу будемо приділяти бінарним відношенням (k = 2), які для стислості будемо називати просто відношеннями, якщо не обумовлено противного. Якщо на Х задано відношення R ( X 2, то запис x R х' означає, що x і х' знаходяться у відношенні R, тобто (x, х') ( R. Областю визначення відношення R називаємо множину (R = {x | (( y : (x, y) ( R}, а областю значень - множину (R = {x | (( y : (y, x) ( R}. Для відношень звичайним чином визначені теоретико-множинні операції об’єднання, перетину і т.д. Доповненням відношення R ( X 2 вважаємо множину
. Оберненим відношенням до відношення R називається відношення, задане множиною R-1 = {(x, y) | (y, x) ( R}. Образом множини Х відносно R називається множина R(Х) = {y | існує таке х ( Х, що (х, у) ( R} прообразом Х відносно R - множина R-1(Х) = {х | існує таке y ( Х, що (х, у) ( R}. Розглянемо кілька прикладів найпростіших відношень: 1) на множині N відношення ( . Ясно, що впорядковані пари (3, 7) і (5, 5) належать цьому відношенню, а пара (4, 1) не належить; 2) на множині Р(Х) всіх підмножин множини Х = {1, 3, 5, 7, 9} відношення (. Пари підмножин ({1, 3}, {1, 3, 9}) і ({5, 7, 9}, {5, 7, 9}) належать цьому відношенню, а пара підмножин ({1, 5, 7}, {3, 5, 9}) не належить. Кожному відношенню R на скінченній множині з n елементів X = {x1, x2, …, xn} можна поставити у відповідність матрицю А = (аij), i,j = 
де aij = 1, якщо xi R xj , і aij = 0 у протилежному випадку. Матриця А, яка складається з елементів 0 та 1, називається матрицею інцидентності відношення R. Ця матриця однозначно задає відношення на скінченних множинах. Наприклад, - одинична матриця задає відношення рівності; - якщо в матриці на головній діагоналі знаходяться 0, а інші елементи рівні 1, то вона задає відношення нерівності. Якщо Х = {1, 2, 3, 4} і R – відношення (, то матриця інцидентності матиме вигляд
Відношення R на множині X називається: 1) рефлективним, якщо довільний елемент множини знаходиться у відношенні сам з собою, тобто для будь-якого х ( Х виконується х R х. Прикладами рефлективних відношень можуть бути ≤, ≥, = на множині натуральних чисел; 2) антирефлективним, якщо для будь-якого х ( Х пара (х, х) не належить до відношення R. Прикладами антирефлективних відношень можуть бути <, >, ≠ на множині раціональних чисел; 3) симетричним, якщо для довільних x, х' ( Х з того, що x R x випливає х' R x; 4) антисиметричним, якщо для довільних x, х' ( Х з того, що x R х' і х' R x, випливає x = х' (наприклад, ( на N, тому що з x ( х' і х' ( x випливає х' = x); 5) транзитивним, якщо для довільних x, х', х'' ( Х з того, що x R х' і х' R х'', випливає x R х'' (наприклад, відноше...